/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.search
 * author:David
 * Date:2016年5月24日下午7:42:00
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.search;

import com.xuwei.base.link.Iterator;
import com.xuwei.base.link.LinkedList;
import com.xuwei.base.link.LinkedListDLNode;

/**
 * 平衡二叉查找树：使用红黑树算法实现
 * 红黑树性质：
 * 1.每个结点或是红色的，或是黑色的
 * 2.根结点是黑色的
 * 3.每个叶结点是黑色的
 * 4.如果一个结点是红色的，则它的两个子结点都是黑色的
 * 5.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。 * 
 * @author David
 * @since 2016年5月24日 下午7:42:00
 * @version 
 * @since JDK 1.6
 */
public class RBTree{
	private RBTreeNode root;
	private RBTreeNode startBN;
	protected final static Strategy strategy = new TreeStrategy();
	public final static RBTreeNode NIL = new RBTreeNode(null, RBTreeNode.BLACK);//哨兵结点
	/**
	 * 
	 */
	public RBTree() {
		this(NIL);
	}
	/**
	 * @param root
	 */
	public RBTree(RBTreeNode root) {
		this.root = root;
	}
	
	public void insert(Object ele) {
		RBTreeNode p = NIL;
		RBTreeNode current = root;
		while(current!=NIL){   //找到待插入位置
			p = current;
			if(strategy.compare(ele, current.getKey())==-1){
				current = current.getlChild();
			}else{
				current =  current.getrChild();
			}
		}
		RBTreeNode newNode = new RBTreeNode(ele);      
		if(p==NIL){
			root = newNode;//树为空
		}else if(strategy.compare(ele, p.getKey())==-1){
			p.setlChild(newNode);
		}else{
			p.setrChild(newNode);
		}
		newNode.setlChild(NIL);
		newNode.setrChild(NIL);
		newNode.setColor(RBTreeNode.RED);
		newNode.setParent(p);
		root = reBalance(newNode);
		
	}
	

	/* 
	 * 左旋示意图：对节点x进行左旋 
	 *     p                       p 
	 *    /                       / 
	 *   x                       y 
	 *  / \                     / \ 
	 * lx  y      ----->       x  ry 
	 *    / \                 / \ 
	 *   ly ry               lx ly 
	 * 左旋做了三件事： 
	 * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时) 
	 * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) 
	 * 3. 将y的左子节点设为x，将x的父节点设为y 
	 */
	private void leftRotate(RBTreeNode x){
		RBTreeNode y = x.getrChild();
		x.setrChild(y.getlChild());//turn y's subtree into x's right subtree
		if(y.hasLChild()){
			y.getlChild().setParent(x);
		}
		RBTreeNode p = x.getParent();
		y.setParent(p); //link x's parent to y
		if(p==NIL){
			root = y;
		}else if(x.isLChild()){
			p.setlChild(y);
		}else{
			p.setrChild(y);
		}
		y.setlChild(x);
		x.setParent(y);
	}
	
	/* 
	 * 右旋示意图：对节点x进行右旋 
	 *        p                   p 
	 *       /                   / 
	 *      x                   y 
	 *     / \                 / \ 
	 *    y  rx   ----->      ly  x 
	 *   / \                     / \ 
	 * ly  ry                   ry rx
	 * 右旋做了三件事： 
	 * 1. 将y的右子节点赋给x的左子节点,并将x赋给y右子节点的父节点(y右子节点非空时) 
	 * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) 
	 * 3. 将y的右子节点设为x，将x的父节点设为y
	 */  
	private void rightRotate(RBTreeNode x){
		RBTreeNode y = x.getlChild();
		x.setlChild(y.getrChild());////turn y's subtree into x's left subtree
		if(y.hasRChild()){
			y.getrChild().setParent(x);
		}
		RBTreeNode p = x.getParent();
		y.setParent(p); //link x's parent to y
		if(p==NIL){
			root = y;
		}else if(x.isLChild()){
			p.setlChild(y);
		}else{
			p.setrChild(y);
		}
		y.setrChild(x);
		x.setParent(y);
	}
	
	
	/**
	 * 重新平衡二叉树
	 * @param node
	 * @return
	 */
	private RBTreeNode reBalance(RBTreeNode node){
		RBTreeNode parent,gparent;
		//父结点的颜色是红色
		while((parent = node.getParent())!=NIL&&parent.isRed()){
			gparent = parent.getParent();
			 //若父节点是祖父节点的左子节点，下面else与其相反  
	        if(parent.isLChild()) {                  
	        	RBTreeNode sibling = gparent.getrChild();//获得兄弟结点
	        	if(sibling.isRed()){      //case1:兄弟结点是红色
	        		parent.setColor(RBTreeNode.BLACK);
	        		sibling.setColor(RBTreeNode.BLACK);
	        		gparent.setColor(RBTreeNode.RED);
	        		node = gparent;//指针上移
	        		continue;
	        	}else if(node.isRChild()){ //case2:兄弟结点是黑色且当前结点是右子结点
	        		node = parent;
	        		leftRotate(node);
	        	}
	        	//case3:兄弟结点是黑色且当前结点是左子结点
	        	parent.setColor(RBTreeNode.BLACK);
	        	gparent.setColor(RBTreeNode.RED);
	        	rightRotate(gparent);
	        }else{
	        	RBTreeNode sibling =  gparent.getlChild();
	        	if(sibling.isRed()){    //case1:兄弟结点是红色
	        		parent.setColor(RBTreeNode.BLACK);
	        		sibling.setColor(RBTreeNode.BLACK);
	        		gparent.setColor(RBTreeNode.RED);
	        		node = gparent;//指针上移
	        		continue;
	        	}else if(node.isLChild()){//case2:兄弟结点是黑色的且当前结点是左子结点
	        		node = parent;
	        		rightRotate(node);
	        	}
	        	//case3:兄弟结点是黑色的且当前结点是右子结点
	        	parent.setColor(RBTreeNode.BLACK);
	        	gparent.setColor(RBTreeNode.RED);
	        	leftRotate(gparent);
	        }
		}
		root.setColor(RBTreeNode.BLACK);
		return root;
	}
	
	
	/**
	 * 返回以v为根在中序遍历序列中的后序结点
	 */
	private RBTreeNode getSuccessor(RBTreeNode v){
		if(v==null){
			return null;
		}
		if(v.hasRChild()){
			return min( v.getrChild());
		}
		while(v.isRChild()){
			v =  v.getParent();
		}
		return  v.getParent();
	}

	/**
	 * 返回以v为根在中序遍历序列中的前驱结点
	 */
	private RBTreeNode getPredecessor(RBTreeNode v){
		if(v==null){
			return null;
		}
		if(v.hasLChild()){
			return max( v.getlChild());
		}
		while(v.isLChild()){
			v =  v.getParent();
		}
		return  v.getParent();
	}
	
	/**
	 * 返回以v为根的二叉查找树中最小元素的位置
	 */
	public RBTreeNode min(RBTreeNode v){
		if(v!=null){
			while(v.hasLChild()){
				v =  v.getlChild();
			}
		}
		return v;
	}
	
	/**
	 * 返回以v为根的二叉查找树中最大元素的位置
	 */
	public RBTreeNode max(RBTreeNode v){
		if(v!=null){
			while(v.hasRChild()){
				v =  v.getrChild();
			}
		}
		return v;
	}

	/**
	 * 中序遍历二叉查找树
	 */
	public Iterator inOrderTree(){
		LinkedList list = new LinkedListDLNode();
		return inOrderTreeRe(root, list).elements();
	}

	/**
	 * 中序遍历递归算法
	 */
	private LinkedList inOrderTreeRe(RBTreeNode node, LinkedList list) {
		if(node.hasLChild()){
			inOrderTreeRe( node.getlChild(), list);
		}
		list.insertLast(node);
		if(node.hasRChild()){
			inOrderTreeRe(node.getrChild(), list);
		}
		return list;
	}
	
}
